// Created by WXX on 2021/9/18 9:53
#include <iostream>
#include <vector>

using namespace std;

/**
 * 执行用时：168 ms, 在所有 C++ 提交中击败了61.12%的用户
 * 内存消耗：55.1 MB, 在所有 C++ 提交中击败了43.91%的用户
 */
class Solution {
public:
    vector<int> f;
    int n, m;

    bool dp(int x) {
        if (f[x] != -1) return f[x];

        int sum = 0;
        for (int i = 0; i < n; i++)
            if (x >> i & 1)
                sum += i + 1;
        for (int i = 0; i < n; i++) {
            if (x >> i & 1) continue;
            if (sum + i + 1 >= m) return f[x] = 1;  // 先手报i+1后和大于m，则获胜
            if (!dp(x + (1 << i))) return f[x] = 1;  // 可以让对方必败，则先手必胜
        }
        return f[x] = 0;  // 没有任何一种方式让对方必败，则先手必败
    }

    bool canIWin(int _n, int _m) {
        n = _n, m = _m;
        f.resize(1 << n, -1);
        if (n * (n + 1) / 2 < m) return false;
        return dp(0);
    }
};

int main() {

    cout << Solution().canIWin(10, 11) << endl;  // false

    return 0;
}
